Buffer insertion provides a number of benefits in electronic systems. Unbuffered connections exhibit quadratic delay growth with increasing distance between source and destination. Insertion of buffers along connections limits the quadratic growth of the delay and makes the growth close to linear. Buffers may also be used to isolate connections to minimize delays along timing critical connections at the expense of non-timing critical connections, reduce signal transition time, improve signal integrity, and slow down signals to improve hold time margins.
Most commercially available EDA tools insert buffers either before and/or after routing without integrating buffer insertion decisions with routing decisions. For example, some commercial tools predict a net topology for a given net in isolation from other nets after placement, when the location of each net's source and destinations are known. Based on the predicted net topology, the tools will select buffer locations that would be optimal for the predicted topology. A routing procedure would then attempt to connect the inserted buffers to sources, sinks, and other buffers. The routed circuit would be analyzed. Unused and suboptimal buffers would be removed from the circuit, and additional buffers would be added where required. The resulting layout would then be passed back to the router. Iterations between the routing procedure and buffer insertion would continue until convergence was achieved. This approach proved to be suboptimal because it selects net topologies and buffer locations one at a time in isolation, ignoring interactions between nets, congestion, and routing blockages.
Thus, what is needed is an efficient method and apparatus for performing buffer insertion during routing.